#define _CRT_SECURE_NO_WARNINGS
//#include<string.h>
//#include<stdio.h>
//int lengthOfLongestSubstring(char* s)
//{
//    int m = 0;
//    int n = 0;
//    char* s1 = s;
//    while (*s1 != 0)
//    {
//        s1 = s + 1;
//        if (*s != *s1)
//        {
//            s1++;
//            m++;
//        }
//        if (*s == *s1)
//        {
//            s = s1;
//            if (n < m)
//            {
//                n = m;
//            }
//        }
//    }
//    return n;
//}
//int main()
//{
//	char str[100];
//	fgets(str, 100, stdin);
//	int len = strlen(str);
//	if (str[len - 1] == '\n')
//	{
//		str[len - 1] = '\0';
//	}
//    int ret = lengthOfLongestSubstring(str);
//    printf("%d", ret);
//	return 0;
//}


//#include<stdio.h>
//int main()
//{
//	int count = 0;
//	int j = 1;
//	int m =1;
//	int mark[302] = { 0 };
//	int n, x;
//	while (scanf("%d %d", &n, &x)&&n!=0&&x!=0)
//	{
//		j = 0;
//		m = 0;
//		while (1)
//		{
//			if (!mark[j])
//			{
//				m++;
//			}
//			if (m == x)
//			{
//				mark[j] = 1;
//				count++;
//			}
//			if (j == n)
//			{
//				
//			}
//			if (count == n - 1)
//			{
//				break;
//			}
//		}
//		j =1;
//		while (1)
//		{
//			if (!mark[j])
//			{
//				printf("%d\n", j);
//				break;
//			}
//			j++;
//		}
//	}
//	return 0;
//}


//#include<stdio.h>
//#include<stdlib.h>
//int process(int n, int m)
//{
//	int* p1 = (int*)malloc(n * sizeof(int));
//	int count = n;
//	int index = 0;
//	for (int i = 0; i < n; i++)
//	{
//		p1[i] = i + 1;
//	}
//	while (count > 1)
//	{
//		index = (index + m - 1) % count;
//		for (int i = index; i < count - 1; i++)
//		{
//			p1[i] = p1[i + 1];
//		}
//		count--;
//	}
//	int y = p1[0];
//	free(p1);
//	return y;
//}
//int main()
//{
//	int n, m;
//	while (scanf("%d %d", &n, &m))
//	{
//		if (m == 0 && n == 0)
//		{
//			break;
//		}
//		printf("%d\n", process(n,m));
//	}
//	return 0;
//}


//#include<stdio.h>
//#include<string.h>
//char* process(char* str, char* sub)
//{
//	char result[100];
//	result[0] = '\0';
//	char* ps = NULL;
//	int len = strlen(sub);
//	while ((ps = strstr(str, sub)) != NULL)
//	{
//		strncat(result, str, ps - str);
//		str = ps + len;
//	}
//	strcat(result, str);
//	return result;
//}
//int main()
//{
//	char str[100];
//	char sub[100];
//	scanf("%s %s", &str, &sub);
//	char* ret = process(str, sub);
//	printf("%s\n", ret);
//	return 0;
//}

//#include<stdio.h>
//#include<string.h>
//char result[100] = { 0 };
//void process(char* str, char* sub)
//{
//    char* ps = NULL;
//    while ((ps = strstr(str, sub)) != NULL)
//    {
//        strncat(result, str, ps - str);
//        int len = strlen(sub);
//        str =ps+len;
//    }
//    strcat(result, str);
//    return;
//}
//int main()
//{
//    char str[100], sub[100];
//    scanf("%s %s", str, sub);
//    process(str, sub);
//    printf("%s", result);
//    return 0;
//}

//#include<stdbool.h>
//#include<stdio.h>
//
//int n;
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//int num[100][100];
//int mark[100][100] = { 0 };
//
//bool is_valid(int x, int y)
//{
//	return x >= 0 && x < n && y >= 0 && y < n;
//}
//
//void process(int x,int y)
//{
//	if (mark[x][y] || !is_valid(x,y) || num[x][y] != 0)
//	{
//		return;
//	}
//	mark[x][y] = 1;
//	for (int i = 0; i < 4; i++)
//	{
//		int nx = x + dx[i];
//		int ny = y + dy[i];
//		process(nx, ny);
//	}
//}
//
//void turn()
//{
//	for (int i = 1; i < n-1; i++)
//	{
//		for (int j =1; j < n-1; j++)
//		{
//			if (mark[i][j] == 0 && num[i][j] == 0)
//			{
//				num[i][j] = 2;
//			}
//		}
//	}
//}
//
//int main()
//{
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < n; j++)
//		{
//			scanf("%d", &num[i][j]);
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		process(0, i);
//		process(n-1,i);
//		process(i,0);
//		process(i,n-1);
//	}
//	turn();
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < n; j++)
//		{
//			printf("%d ",num[i][j]);
//		}
//		printf("\n");
//	}
//	return 0;
//}

//#include <string.h>
//int rplStrFirst(char* str, char* sub, char* rpl, int start) 
//{
//    int subLen = strlen(sub); 
//    int rplLen = strlen(rpl);
//    char* pos = strstr(str + start, sub);
//    if (pos == NULL) 
//    {
//        return -1;
//    }
//    int index = pos - str;
//    memmove(pos + rplLen, pos + subLen, strlen(pos) - subLen + 1);
//    memcpy(pos, rpl, rplLen);
//    return index + rplLen;
//}


#include <stdio.h>
#include <string.h>

//int getIndex(char* str, char* sub, int pos)
//{
//    if (*sub == '\0')
//    {
//        return 0;
//    }
//    char* found = strstr(str + pos, sub);
//    if (found != NULL) 
//    {
//        return found - str;
//    }
//    return -1;
//}

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

//bool delStrFirst(char* str, char* sub)
//{
//    char* pos = strstr(str, sub);
//    if (pos == NULL) 
//    {
//        return false;
//    }
//    int subLen = strlen(sub);
//    memmove(pos, pos + subLen, strlen(pos) - subLen + 1);
//    return true;
//}


//bool rplStr(char* str, char* sub, char* rpl)
//{
//    int start = 0;
//    while (true)
//    {
//        int newPos = rplStrFirst(str, sub, rpl, start);
//        if (newPos == -1)
//        {
//            break;
//        }
//        start = newPos;
//    }
//    return true;
//}

//#include<stdio.h>
//#include<string.h>
//#include<ctype.h>
//int main()
//{
//	char str[100];
//	gets(str);
//	int len = strlen(str);
//	for (int i = 0; i < len; i++)
//	{
//		if (islower(str[i]))
//		{
//			str[i] -= 32;
//		}
//	}
//	for (int i = 0; i < len; i++)
//	{
//		printf("%c ", str[i]);
//	}
//	return 0;
//}

